Năm 2011, Fernandes được gọi lên đội tuyển Brasil để đá trận Siêu kinh điển Nam Mỹ, nhưng anh đã từ chối với lý do cá nhân. Fernandes có trận đấu ra mắt Brasil trong trận thắng 4–0 trước Nhật Bản vào ngày 14 tháng 10 năm 2014.[4]

Sau khi trở thành công dân Nga, Fernandes quyết định chuyển sang khoác áo đội tuyển quốc gia Nga và được triệu tập tham dự 2 trận đấu giao hữu gặp Thổ Nhĩ Kỳ vào ngày 31 tháng 6 và Ghana vào ngày 6 tháng 9 năm 2016. Tuy nhiên, Fernaldes là cầu thủ của CSKA Moscow kể từ tháng 4 năm 2012, điều đó có nghĩa rằng tại thời điểm đó, anh đã không sống ở Nga liên tục trong ít nhất 5 năm. Do đó, anh không đủ điều kiện chơi cho tuyển Nga cho đến tháng 4 năm 2017.

Ngày 23 tháng 3 năm 2017, có thông tin rằng Fernaldes sẽ ra mắt đội tuyển Nga vào 24 tháng 3 trong trận giao hữu với Bờ Biển Ngà, nhưng anh đã không ra sân trong trận đấu đó.[5] Anh có trận ra mắt chính thức cho Nga trong trận giao hữu với đội tuyển Hàn Quốc ngày 7 tháng 10 năm 2017.[6]

Tại World Cup 2018 tổ chức tại Nga, anh đóng một vai trò quan trọng trong màn trình diễn của đội chủ nhà.[7] Ở trận tứ kết gặp đội Croatia, anh đã ghi bàn gỡ hoà 2-2 ở hiệp phụ để đưa trận đấu vào loạt luân lưu. Tuy nhiên sau đó, Fernandes đã đá hỏng ở lượt của mình và Nga để thua Croatia 3-4 trong loạt sút luân lưu.[8]